package lc;
import org.junit.*;
public class Ex525 {
    class Solution {
        public int findMaxLength(int[] nums) {
            int n = nums.length, max = 0;
            if (n <= 1) {
                return max;
            }
            //f[i][j] 表示nums[i:j+1]是否是0,1相同
            //> 0, 1多的个数， <0, 0多的个数， 0:0,1相同
            int[][] f = new int[n][n];
            for (int i = 0; i < n; i++) {
                f[i][i] = nums[i] == 1 ? 1 : -1;
            }
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    f[i][j] = f[i][j - 1] + (nums[j] == 1 ? 1 : -1);
                    if (f[i][j] == 0) {
                        max = Math.max(max, j - i + 1);
                    }
                }
            }
            return max;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{0,1,1,0,1,0,1,1,0,1,0,0,0,0,1,0,1,1,1,0,1,0,1,0,0,1,1,0,0,1,0,1,1,1,0,
            1,0,1,1,1,1,1,0,1,0,0,1,0,1,0,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0,0,0,1,1
            ,1,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,1,1,0,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,1};
        System.out.println(s.findMaxLength(nums));
    }
    
}
